//有 n 个网络节点，标记为 1 到 n。 
//
// 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， 
//wi 是一个信号从源节点传递到目标节点的时间。 
//
// 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：times = [[1,2,1]], n = 2, k = 1
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：times = [[1,2,1]], n = 2, k = 2
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= n <= 100 
// 1 <= times.length <= 6000 
// times[i].length == 3 
// 1 <= ui, vi <= n 
// ui != vi 
// 0 <= wi <= 100 
// 所有 (ui, vi) 对都 互不相同（即，不含重复边） 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 图 | 最短路 | 堆（优先队列） 
//
// 👍 558, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

class NetworkDelayTime {
    public static void main(String[] args) {
        Solution solution = new NetworkDelayTime().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 参照labuladong:https://labuladong.github.io/algo/2/21/56/
        public int networkDelayTime(int[][] times, int n, int k) {
            // 下标从1开始
            List<int[]>[] graph = new LinkedList[n + 1];
            for (int i = 0; i <= n; i++) {
                graph[i] = new LinkedList<>();
            }

            for (int[] time : times) {
                int from = time[0], to = time[1], weight = time[2];
                graph[from].add(new int[]{to, weight});
            }

            // 使用dijkstra计算最短路径
            int[] dijkstra = dijkstra(k, graph);

            int maxTime = 0;
            for (int i = 1; i < dijkstra.length; i++) {
                // 有不可达的情况
                if (dijkstra[i] == Integer.MAX_VALUE) return -1;
                maxTime = Math.max(maxTime, dijkstra[i]);
            }

            return maxTime;
        }

        class Status {
            // 图节点的 id
            int id;
            // 从 start 节点到当前节点的距离
            int distFromStart;

            public Status() {
            }

            public Status(int id, int distFromStart) {
                this.id = id;
                this.distFromStart = distFromStart;
            }
        }

        // 输入一个起点 start，计算从 start 到其他节点的最短距离
        int[] dijkstra(int start, List<int[]>[] graph) {
            // 定义：distTo[i] 的值就是起点 start 到达节点 i 的最短路径权重
            int[] distTo = new int[graph.length];
            Arrays.fill(distTo, Integer.MAX_VALUE);
            distTo[start] = 0;
            PriorityQueue<Status> queue = new PriorityQueue<>((a, b) -> a.distFromStart - b.distFromStart);
            queue.offer(new Status(start, 0));

            while (!queue.isEmpty()) {
                Status status = queue.poll();
                int curNodeId = status.id;
                int curDistFromStart = status.distFromStart;

                if (curDistFromStart > distTo[curNodeId]) {
                    continue;
                }

                for (int[] neighbor : graph[curNodeId]) {
                    int nextNodeId = neighbor[0];
                    int distToNextNode = distTo[curNodeId] + neighbor[1];
                    if (distToNextNode < distTo[nextNodeId]) {
                        distTo[nextNodeId] = distToNextNode;
                        queue.offer(new Status(nextNodeId, distToNextNode));
                    }
                }
            }

            return distTo;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
